#include<iostream>

using namespace std;

struct ListNode{
    int value;
    ListNode * next;
};

// 尾插
ListNode * createNode(int * data, int length){
    if ( data == nullptr || length <= 0 )
        return nullptr;
    ListNode * head = new ListNode();
    head -> value = data[0];
    head -> next = nullptr;
    ListNode * pHead = head;
    for ( int i=1;i<length; i++ ){
        ListNode * node = new ListNode();
        node -> value = data[i];
        node -> next = nullptr;
        pHead = pHead -> next = node;
    }
    return head;
}

ListNode * mergeSortedLists(ListNode * headA, ListNode * headB){
    if ( headA == nullptr && headB == nullptr )
        return nullptr;
    // 添加带头结点的链表
    ListNode * newHead = new ListNode();
    ListNode * newListTail = newHead;
    while ( headA != nullptr && headB != nullptr ){
        if ( headA->value > headB -> value ){
            newListTail = newListTail -> next = headB;
            headB = headB -> next;
        }else {
            newListTail = newListTail -> next = headA;
            headA = headA -> next;
        }
    }

    if ( headA == nullptr ){
        newListTail -> next = headB;
    }
    if ( headB == nullptr ){
        newListTail -> next = headA;
    }
    return newHead->next;
}

void printNode(ListNode * head){

    ListNode * pHead = head;
    while ( pHead != nullptr ){
        cout << pHead ->value << endl;
        pHead = pHead -> next;
    }
}

int main(void){
    // Test 1
    int data1[] = {1,2,3,4,5,6,7,8,9};
    int data2[] = {0,2,3,5,6,7,9,10,18};
    // Test 2
    int data1[] = {};
    int data2[] = {0,2,3,5,6,7,9,10,18};
    // Test 3
    int data1[] = {};
    int data2[] = {};

    ListNode * headA = createNode(data1, sizeof(data1)/sizeof(int));
    ListNode * headB = createNode(data2, sizeof(data2)/sizeof(int));
    printNode(headA);
    cout << "-----"<< endl;
    printNode(headB);
    cout << "-----"<< endl;
    ListNode * mergeNodeHead = mergeSortedLists(headA, headB);
    printNode(mergeNodeHead);
    return 0;
}